package com.company.algo.DichotomousSearch;

/**
 * 875. 爱吃香蕉的珂珂
 */
public class kokoEatingBananas {
    public int minEatingSpeed(int[] piles, int h) {
        int max = getMax(piles);
        // for(int speed = 1; speed < max; speed++){
        //     if(canFinish(piles,speed,h)) return speed;
        // }
        // return max;
        //使用二分查找优化
        int left = 1, right = max+1;
        while(left < right){
            int mid = left + (right - left)/2;
            //说明mid>=最合适的速度
            if(canFinish(piles,mid,h)) right = mid;
            else left = mid + 1;
        }
        return left;
    }
    public int getMax(int[] piles){
        int res = 0;
        for(int x: piles){
            res = Math.max(res,x);
        }
        return res;
    }
    public boolean canFinish(int[] piles, int speed, int h){
        int time = 0;
        for(int n: piles){
            time += timeOf(n, speed);
        }
        return time <= h;
    }
    public int timeOf(int n, int speed){
        //除法向上取整
        return (n/speed)+(n % speed > 0 ? 1 : 0);
    }
}
